package struct.arrays;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author: kanggw
 * @date: 2022/2/28

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。
　示例 1：

输入：[3,2,3]
输出：3
示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 */
public class MajorityNumbers {

    public static void main(String[] args) {

        int[] nums = {2, 1, 2};

        //final int sorts = sorts(nums);
        //System.out.println("out:" + sorts);

        final int i = useMap(nums);
        System.out.println("out:" + i);

        final int i1 = majorityElement(nums);

        System.out.println("out:" + i1);

    }

    /**
     * 题中说了给定的数组总是存在多数元素。，也就是说肯定有一个元素的个数大于数组长度的一半。我们只需要把这个数组排序，那么数组中间的值肯定是存在最多的元素。
     *
     * 其实很容易证明，假设排序之后数组的中间值不是最多的元素，那么这个最多的元素要么是在数组前半部分，要么是在数组的后半部分，无论在哪，他的长度都不可能超过数组长度的一半。
     * @return
     */
    public static int sorts(int[] nums) {

        Arrays.sort(nums);

        return nums[nums.length/2];
    }

    /**
     * 还可以使用Map来解决，map的key存放的是数组中的元素，value是数组中元素的个数，把数组中元素不断的存放到map中，如果某个元素的个数大于数组长度的一半，直接返回。

     * @param nums
     * @return
     */
    public static int useMap(int[] nums) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int item : nums) {

            final Integer orDefault = map.getOrDefault(item, 0) + 1;
            if (orDefault > nums.length / 2) {
                return item;
            } else {
                map.put(item, orDefault);
            }

        }
        return 0;
    }

    /**
     * 摩尔投票法
     * 假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。
     *
     * 就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。

     * @return
     */
    public static int majorityElement(int[] nums) {

        int major = nums[0];
        int count = 1;

        for (int i = 1; i < nums.length; i++) {

            if (count == 0) {
                major = nums[i];
                count++;
            } else if (major == nums[i]) {
                count++;
            } else {
                count--;
            }

        }

        return major;
    }

}
